package com.study.dp;

/**
 * 动态规划
 * <p>
 * 爬楼梯问题：有n个台阶，一次可以爬1阶或2阶或三阶 ，一共有一种爬发
 *
 * @author yyb8152
 * @since 20220901
 **/
public class DynamicPlanning {
    public static void main(String[] args) {

        Integer run = getRun(4);
        System.out.println(run);
        System.out.println("-------简化方法---------");
        System.out.println(countWays(5));

    }

    // 时间复杂复杂度是O(3^n) 空间复杂度O(n)
    public static Integer getRun(Integer n) {
        // 递归的基线条件：可以爬1阶
        if (n == 0 || n == 1) {
            return 1;
        }
        // 可以爬1阶或2阶
        if (n == 2) {
            return 2;
        }

        // 递归条进:一次走了一步，剩余的步数
        Integer step1 = getRun(n - 1);

        //类似的一次走2步
        Integer step2 = getRun(n - 2);

        // 类似的一次走3步
        Integer step3 = getRun(n - 3);

        return step1 + step2 + step3;

    }

    public static Integer countWays(Integer n) {
        int[] step = new int[n + 1];

        if (n < 2) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        step[1] = 1;
        step[2] = 2;
        step[3] = 4;
        // 一共有三种走法。
        for (int i = 4; i < step.length; i++) {
            step[i] = step[i - 1] + step[i - 2] + step[i - 3];

        }
        return step[n];
    }
}
